//
//  Problem696.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/18.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 696. 计数二进制子串
 给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
 重复出现的子串要计算它们出现的次数。
 示例 1 :
     输入: "00110011"
     输出: 6
     解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
     请注意，一些重复出现的子串要计算它们出现的次数。
     另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
 示例 2 :
     输入: "10101"
     输出: 4
     解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

 提示：

 s.length 在1到50,000之间。
 s 只包含“0”或“1”字符。
 */
@objcMembers class Problem696: NSObject {
    func solution() {
//        print(countBinarySubstringsCenter("00110011"))
//        print(countBinarySubstringsCenter("10101"))
        print(countBinarySubstringsCenter("1010001"))
    }
    
    /*
     暴力破解
     */
    func countBinarySubstrings(_ s: String) -> Int {
        var num = 0
        let charts = Array(s)
        for i in 0..<charts.count-1 {
            for j in i+1..<charts.count {
                if (j - i) % 2 == 0 {   // 奇数不符合
                    continue
                }
                
                if isBinarySubstring(charts, i, j) {
                    num += 1
                }
            }
        }
        return num
    }
    
    func isBinarySubstring(_ charts:[Character], _ start: Int, _ end: Int) -> Bool {
        let startC : Character = charts[start]
        let endC   : Character = charts[end]
        
        if startC == endC {
            return false
        }
        
        var i = start + 1
        var j = end - 1
        while i < j {
            if charts[i] == charts[j] {
                return false
            }
            if charts[i] != startC {
                return false
            }
            if charts[j] != endC {
                return false
            }
            
            i += 1
            j -= 1
        }
        
        return true
    }
    
    /*
     中线点：
     重点：
     1: 符合要求的子字符串必定是偶数个
     2: 最中心的2个字符要不是：01 要不是 10
     步骤
     1: 遍历字符串,每次取连续的2个字符 c1、c2
     2: 如果c1 == c2不符合要求
     3: c1 != c2向左右扩展一步，判断是否符合
     */
    
    func countBinarySubstringsCenter(_ s: String) -> Int {
        var num = 0
        let charts = Array(s)
        for i in 0..<charts.count-1 {
            if charts[i] == charts[i+1] {
                continue
            }
            
            num += 1
            var left = i-1
            var right = i+2
            while left >= 0 && right < charts.count {
                if charts[left] == charts[i], charts[right] == charts[i+1] {
                    num += 1
                } else {
                    break
                }
                left -= 1
                right += 1
            }
        }
        return num
    }
    
    /*
     字符串ss按照连续的 0 和 1 进行分组，例如 s = 00111011 => counts={2,3,1,2}。 2个连续的0，3个连续1，1个连续0，2个连续1
     counts前2个：表示 00111, 最多有2个，因为0只有2个
     */
    func countBinarySubstringsUser(_ s: String) -> Int {
        var result = 0
        var currentChar:Character = "2"
        var lastLength = 0
        var currentLength = 0
        
        for char in s {
            if currentChar != char {
                result += min(currentLength, lastLength)
                currentChar = char
                lastLength = currentLength
                currentLength = 1
            }else {
                currentLength += 1      // 计算当前字符的个数
            }
        }
        result += min(currentLength, lastLength)
        return result
    }

}
